<?php
// +----------------------------------------------------------------------
// | 算法三：贪心法 ( Greedy ) /贪婪法
// | 基本思想：
// | 典型实例：
// |   1）活动选择问题  O(n)
// |   2）背包问题     O(n)
// +----------------------------------------------------------------------

namespace helper\algorithm;

class Greedy
{
    public function demo()
    {
        $n = 5;
        $w = 100;

        $weight = [10,20,30,40,50];
        $value  = [20,30,65,40,60];

        // 1）按照最大价值先放原则
        // {1,1,1/3,1,0} 65+60+20+10*1.5=160

        // 2）按照最小重量先放原则
        // {1,1,1,0,1} 20+30+65+40=155

        // 3）按最大单位重量先放原则
        // {1,1,1,4/5,1} 65+20+60*4/5=163

        // 按单位重量的价值从大到小排序,时间复杂度：O(nlgn)
        $product = [];
        foreach ($weight as $k => $v) {
            $product[] = ['weight' => $v, 'value' => $value[$k], 'vm' => round( $value[$k] / $v, 1)];
        }
        $product = $this->sortByKey($product, 'vm');
        //weight[30, 10, 20, 50, 40];
        //value[65, 20, 30, 60, 40];
        //vm [2.1, 2, 1.5, 1.2, 1];

        $res = $this->knapsack($n, $w, $product['value'], $product['weight']);
        print_r($res);
    }

    /**
     * 背包问题
     * 按最大单位重量先放原则
     * @param int $n
     * @param int $w
     * @param array $value
     * @param array $weight
     * @return array
     */
    public function knapsack(int $n, int $w, array $value, array $weight)
    {
        // 初始化
        $x = [];
        //for ($i = 0; $i < $n; $i++) {
        //    $x[$i] = 0;
        //}
        for ($i = 0; $i < $n; $i++) {
            $x[$i] = 0;
            // 如果背包剩余容量可以装卸该物品
            if ($weight[$i] <= $w) {
                $x[$i] = 1;
                $w = $w - $weight[$i];
            } else {
                break;
            }
        }
        // 如果还有部分物品可以装入背包中
        if ($i < $n) {
            $x[$i] = $w / $weight[$i];
        }
        return $x;
    }

    /**
     * 二维数组按key排序
     * @param array $product
     * @param string $key
     * @return array
     */
    private function sortByKey(array $product, string $key): array
    {
        for ($i = 0; $i < count($product); $i++) {
            for ($j = $i + 1; $j < count($product); $j++) {
                if ($product[$i][$key] < $product[$j][$key]) {
                    $temp = $product[$i];
                    $product[$i] = $product[$j];
                    $product[$j] = $temp;
                }
            }
        }
        return $product;
    }
}